import collections
import logging
import operator
import os
import subprocess
import sys
import time

from bisect import bisect, bisect_left
from os.path import basename, dirname

import pipe

# Use the same default ignored directories as ack (http://betterthangrep.com/).
# Seems like a reasonable set to use.
DEFAULT_IGNORE_DIRS = [
	"autom4te.cache", "blib", "_build", ".bzr", ".cdv", "cover_db",
	"CVS", "_darcs", "~.dep", "~.dot", ".git", ".hg", "~.nib", ".pc",
	"~.plst", "RCS", "SCCS", "_sgbak", ".svn"]

INDEX_LOGGING_RATE = 10000

class Match(object):
	
	def __init__(self, filenames, paths, start, end):
		self._filenames = filenames
		self._paths = paths
		self.start = start
		self.end = end

	def paths(self):
		"""Iterate over all the paths in this match."""
		for filename in self.filenames():
			for path in self._paths[filename]:
				yield path

	def filenames(self):
		"""Iterate over all the filenames in this match."""
		for i in xrange(start, end):
			yield self._filenames[i]

class Index(object):
	
	def __init__(self):
		self.filenames = []
		self.paths = {}
	
	def size(self):
		return sum(len(paths) for paths in self.paths.itervalues())

	def _find_first(self, x, exact=False):
		"""Return the index of the first value begins with or equals x."""
	
		lst = self.filenames
		matches = operator.eq if exact else str.startswith

		i = bisect_left(lst, x)
		if i != len(lst) and matches(lst[i], x):
			return i
		return -1

	def add(self, path):
		"""Add the given file to the index if it's not already in it."""

		lst = self.filenames
		name = os.path.basename(path)
		i = bisect_left(lst, name)
		if i < 0 or i >= len(lst) or lst[i] != name:
			lst.insert(i, name)
		self.paths.setdefault(name, set()).add(path)

	def match(self, prefix):
		"""Search for filenames that start with the given prefix.
		
		Return a tuple (start, end) indicating where the matching filenames
		are found in the list. Return None if no matches are found.

		"""
		start = self._find_first(prefix)
		print "found first:", start
		if start >= 0:
			end = bisect(self.filenames, prefix, lo=start)
			return Match(self.filenames, self.paths, start, end)
		return None

	def iterpaths(self, start, end):
		"""Iterate over the paths corresponding to """

	def _process_line(self, line):
		path = str(line).rstrip(os.linesep)
		if os.path.isfile(path):
			self._files_indexed += 1
			if self._files_indexed % INDEX_LOGGING_RATE == 0:
				logging.info("Indexing continues at %.1f files/s." %
					(self._files_indexed / (time.time() - self._indexing_start)))
			self.add(path)

	def _indexing_complete(self):
		logging.info("Indexing took %.2fs for %d files." %
			(time.time() - self._indexing_start, self._files_indexed))

	def add_all(self, dir, ignore_dirs=None, blocking=False):
		if ignore_dirs is None:
			ignore_dirs = DEFAULT_IGNORE_DIRS

		args = ["find", dir, "-type", "d", "("]
		for d in ignore_dirs:
			args.append("-name")
			args.append(d)
			args.append("-o")
		if args[-1] == "-o":
			args.pop()
		args += [")", "-prune", "-o", "-print"]
		p = subprocess.Popen(args, stdout=subprocess.PIPE)
		reader = pipe.LineReader(p.stdout)
		reader.nextLine.connect(self._process_line)
		reader.done.connect(self._indexing_complete)

		# Capture some performance numbers.
		self._indexing_start = time.time()
		self._files_indexed = 0

		reader.read_all(spawn_thread=True)
		if blocking:
			reader.wait()
